﻿namespace Leetcode.N1690;
public class Solution
{
    public int StoneGameVII(int[] stones)
    {
        var n = stones.Length;
        var sums = new int[n + 1];
        for (int i = 1; i < sums.Length; i++)
        {
            sums[i] = sums[i - 1] + stones[i - 1];
        }

        var ans = new (int max, int nextIndex)[n][];
        ans[0] = new (int max, int nextIndex)[n];
        for (int i = 1; i < n; i++)
        {
            ans[i] = new (int max, int nextIndex)[n];
            for (int j = 0; j < n - i; j++)
            {
                if (i == 1)
                {
                    var maxIndex = (stones[j] >= stones[j + 1]) ? j : j + 1;
                    ans[i][j] = (stones[maxIndex], maxIndex == j ? j + 1 : j);
                }
                else
                {
                    var from = j;
                    var to = j + i;

                    var left = sums[to + 1] - sums[from + 1];
                    var rightOfLeft = ans[i - 1][from + 1];
                    var leftNext = ans[i - 2][rightOfLeft.nextIndex];

                    var right = sums[to] - sums[from];
                    var leftOfRight = ans[i - 1][from];
                    var rightNext = ans[i - 2][leftOfRight.nextIndex];
                    if (left + leftNext.max - rightOfLeft.max >= right + rightNext.max - leftOfRight.max)
                    {

                        ans[i][j] = (left + leftNext.max, from + 1);
                    }
                    else
                    {
                        ans[i][j] = (right + rightNext.max, from);
                    }
                }
            }
        }
        var alice = ans[n - 1][0];
        var bob = ans[n - 2][alice.nextIndex];
        return alice.max - bob.max;
    }
}